package mcMST;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class MSTGenotype {
	private List<Integer> prueferNumber;
	private Random rand = new Random();

	/**
	 * Tworzy losowy genotyp dla podanej jako argument liczby wierzcholkow
	 * Wykorzystuje tzw. Pruefer number
	 * @param numOfCities
	 */
	public MSTGenotype(int numOfNodes) {
		Integer [][] matrix;
		Integer [] nodesMatrix;

		prueferNumber = new ArrayList<Integer>(numOfNodes - 2);
		matrix = new Integer [numOfNodes][numOfNodes]; //macierz adiacencji drzewa
		nodesMatrix = new Integer[numOfNodes];

		List<Integer> nodes = new ArrayList<Integer>(numOfNodes);
		List<Integer> usedNodes = new ArrayList<Integer>(numOfNodes);

		for (int nodeNum = 0; nodeNum < numOfNodes; nodeNum++) {
			nodes.add(nodeNum);
		}

		// Wyzerowanie macierzy adiacencji
		for(int i = 0; i < numOfNodes; i++) {
			for(int j = 0; j < numOfNodes; j++) {
				matrix[i][j] = 0;
			}
		}

		for(int i = 0; i < numOfNodes; i++) {
			nodesMatrix[i] = 0;
		}

		// utworzenie drzewa
		int node = nodes.remove(rand.nextInt(nodes.size()));
		usedNodes.add(node);
		int usedNode;
		for (int nodeNum = 0; nodeNum < (numOfNodes - 1); nodeNum++) {
			node = nodes.remove(rand.nextInt(nodes.size()));
			usedNode = usedNodes.get(rand.nextInt(usedNodes.size()));
			usedNodes.add(node);

			matrix[node][usedNode]++;
			matrix[usedNode][node]++;

			nodesMatrix[node]++;
			nodesMatrix[usedNode]++;

			//Debug
			//System.out.println("krawedz " + node + " " + usedNode);
		}


		//Debug
		/*for(int i = 0; i < numOfNodes; i++) {
			for(int j = 0; j < numOfNodes; j++) {
				//Debug
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
		for(int i = 0; i < numOfNodes; i++) {
			System.out.print(nodesMatrix[i] + " ");
		}*/


		//utworzenie Pruefer number
		int succ = 0;
		Boolean vis = true;

		while(vis) {
			vis = false;
			for(int i = 0; i < numOfNodes; i++) {
				if(nodesMatrix[i] == 1) {
					vis = true;
					for(int j = 0; j < numOfNodes; j++) {
						if(matrix[i][j] == 1) {
							succ = j;
							matrix[i][j] = 0;
							matrix[j][i] = 0;
							nodesMatrix[i] --;
							nodesMatrix[j]--;
							break;
						}
					}
					prueferNumber.add(succ);
					break;
				}
			}
		}

		// Debug
		/*System.out.println();
		System.out.println();
		for(int i = 0; i < numOfNodes - 2; i++) {
			System.out.print(prueferNumber.get(i) + " ");
		}
		System.out.println();*/
	}


	/*public static void main(String args[]) {
		MSTGenotype gen = new MSTGenotype(6);
	}*/
	public MSTGenotype(List<Integer> prueferNumber) {
		this.prueferNumber = prueferNumber;
	}

	public MSTGenotype(MSTGenotype mstGenotype) {
		this.prueferNumber = new ArrayList<Integer>(mstGenotype.getPrueferNumber());
	}

	List<Integer> getPrueferNumber() {
		return this.prueferNumber;
	}

	public void setPrueferNumber(List<Integer> prueferNumber) {
		this.prueferNumber = prueferNumber;
	}

	/*

    public int getRandomNodeNumOtherThan(int firstNode) {
        while (true) {
            int rand = getRandomNodeNum();
            if (rand != firstNode) {
                return rand;
            }
        }
    }

    public int getNextNode(int firstNode) {

        int firstNodeIndex = treeOrder.indexOf(firstNode);
        return treeOrder.get(firstNodeIndex + 1);
    }

    public boolean nodeIsLast(int firstNode) {

        if (treeOrder.indexOf(firstNode) == treeOrder.size() - 1) {
            return true;
        } else {
            return false;
        }
    }*/

	/**
	 * Inverse the section from the next node of nodes <i>firstNode</i> to the node <i>secondNode</i>
	 * @param firstNode
	 * @param secondNode
	 */
	/*public void inverse(int firstNode, int secondNode) {
        int firstNodeIndex = treeOrder.indexOf(firstNode);
        int secondNodeIndex = treeOrder.indexOf(secondNode);

        if (firstNodeIndex > secondNodeIndex) {
            int temp = firstNodeIndex;
            firstNodeIndex = secondNodeIndex;
            secondNodeIndex = temp;
        }
        Collections.reverse(treeOrder.subList(firstNodeIndex+1, secondNodeIndex));
    }*/

}

